HDU_5101

题解

这套题能想出来就很简单了。

1、首先我把班级里的人按iq排序，那么任意一个同学就知道有多少人iq比他高了。
2、把所有人放在一起，排个序。
3、枚举每个同学i，在所有人中找出iq之和大于k的那个人j，可以知道在不考虑相同班级的情况下有多少对匹配。（lower_bound）
4、在i同学班级里找智商大于j同学的人数，是同班级但是又重复算的。
5、3步骤-4步骤就行。最后别忘了除以2。

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <stdio.h>
#include <queue>
#include <iostream>
#include <algorithm>
using namespace std;
#define LL long long
const int MAXN=10010;
LL iqs[1005][105];
LL all[100010];
int main()
{
    int t;cin>>t;
    while(t--){
        LL n,k,cnt=0;
        scanf("%I64d%I64d",&n,&k);
        for(int i=1;i<=n;i++){
            scanf("%I64d",&iqs[i][0]);
            for(int j=1;j<=iqs[i][0];j++){
                scanf("%I64d",&iqs[i][j]);
                all[++cnt]=iqs[i][j];
            }
            sort(iqs[i]+1,iqs[i]+1+iqs[i][0]);
        }
        sort(all+1,all+1+cnt);
        LL ans=0,tmp,pos,same;
        for(int i=1;i<=n;i++){
            for(int j=1;j<=iqs[i][0];j++){
                tmp=iqs[i][j];
                pos=upper_bound(all+1,all+1+cnt,k-tmp)-all;
                same=lower_bound(iqs[i]+1,iqs[i]+1+iqs[i][0],all[pos])-iqs[i];
                ans+=cnt+1-pos-(iqs[i][0]+1-same);
            }
        }
        printf("%I64d\n",ans/2);
    }
    return 0;
}